package com.husk.leetcode.tree;

import java.util.*;

/**
 * <p>
 *
 * </p>
 *
 * @author hushunke@sm.vvip-u.com
 * @since 2021/3/23
 */
public class Solution {


    private TreeNode ans;

    /**
     * #68 #236 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     *
     * @param root 二叉树
     * @param p    节点
     * @param q    节点
     * @return
     * @link https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return ans;
    }

    private boolean dfs(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null) {
            return false;
        }
        boolean left = this.dfs(node.left, p, q);
        boolean right = this.dfs(node.right, p, q);
        if ((left && right) || ((node.val == p.val || node.val == q.val) && (left || right))) {
            ans = node;
        }
        return left || right || (node.val == p.val || node.val == q.val);
    }


    /**
     * 检验两个树结构相同
     * <p>
     * https://leetcode-cn.com/problems/same-tree/
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return this.testTreeEqual(p, q);
    }

    public boolean testTreeEqual(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        boolean left = this.testTreeEqual(p.left, q.left);
        boolean right = this.testTreeEqual(p.right, q.right);
        return left && right && p.val == q.val;
    }


    /**
     * 101. 对称二叉树
     * <p>
     * https://leetcode-cn.com/problems/symmetric-tree/
     * <p>
     * 广度优先
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        return this.check(root.left, root.right);
    }

    private boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        return left.val == right.val && this.check(left.left, right.right) && this.check(left.right, right.left);
    }

    private boolean check2(TreeNode left, TreeNode right) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(left);
        queue.offer(right);
        while (!queue.isEmpty()) {
            left = queue.poll();
            right = queue.poll();
            if (left == null && right == null) {
                continue;
            }
            if ((left == null || right == null) || left.val != right.val) {
                return false;
            }

            queue.offer(left.left);
            queue.offer(right.right);

            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }


    /**
     * 102. 二叉树的层序遍历
     * <p>
     * https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int currentLevelSize = queue.size();
            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(level);
        }
        return result;
    }

    /**
     * 104. 二叉树的最大深度
     * <p>
     * https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = this.maxDepth(root.left);
        int right = this.maxDepth(root.right);
        return Math.max(left, right) + 1;
    }

    /**
     * 103. 二叉树的锯齿形层序遍历
     * <p>
     * https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
     *
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int deep = 0;
        while (!queue.isEmpty()) {
            Deque<Integer> list = new LinkedList<>();
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                if (deep % 2 == 0) {
                    list.offerLast(node.val);
                } else {
                    list.offerFirst(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            deep++;
            result.add(new LinkedList<>(list));
        }
        return result;
    }

    /**
     * 105. 从前序与中序遍历序列构造二叉树
     * <p>
     * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
     *
     * @param preorder 前序遍历 preorder = [3,9,20,15,7]
     * @param inorder  中序遍历 inorder = [9,3,15,20,7]
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // TODO

        return null;
    }

    /**
     * 106. 从中序与后序遍历序列构造二叉树
     * <p>
     * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
     *
     * @param inorder
     * @param postorder
     * @return
     */
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        // TODO

        return null;
    }

    /**
     * 107. 二叉树的层序遍历 II
     * <p>
     * https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> deque = new LinkedList<>();
        if (root == null) {
            return deque;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            deque.offerFirst(level);
        }
        return deque;
    }

    /**
     * 108. 将有序数组转换为二叉搜索树
     * <p>
     * https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
     *
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {

        return null;
    }

    /**
     * 111. 二叉树的最小深度
     * <p>
     * https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
     *
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int min = Integer.MAX_VALUE;
        if (root.left != null) {
            min = Math.min(this.minDepth(root.left), min);
        }
        if (root.right != null) {
            min = Math.min(this.minDepth(root.right), min);
        }
        return min + 1;
    }

    /**
     * 118. 杨辉三角
     * <p>
     * https://leetcode-cn.com/problems/pascals-triangle/
     *
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new LinkedList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> line = new LinkedList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    line.add(1);
                } else {
                    line.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));
                }
            }
            result.add(line);
        }
        return result;
    }

    /**
     * 119. 杨辉三角 II
     * <p>
     * https://leetcode-cn.com/problems/pascals-triangle-ii/
     *
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> result = this.generate(rowIndex + 1);
        return result.get(rowIndex);
    }


    /**
     * 112. 路径总和
     * <p>
     * https://leetcode-cn.com/problems/path-sum/
     *
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> valQueue = new LinkedList<>();

        queue.offer(root);
        valQueue.offer(root.val);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            Integer temp = valQueue.poll();
            if (node.left == null && node.right == null) {
                if (targetSum == temp) {
                    return true;
                }
            }
            if (node.left != null) {
                queue.offer(node.left);
                valQueue.offer(temp + node.left.val);
            }
            if (node.right != null) {
                queue.offer(node.right);
                valQueue.offer(node.right.val + temp);
            }
        }
        return false;
    }

    /**
     * 113. 路径总和 II
     * <p>
     * https://leetcode-cn.com/problems/path-sum-ii/
     *
     * @param root
     * @param targetSum
     * @return
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return result;
        }
        Map<TreeNode, TreeNode> map = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> valQueue = new LinkedList<>();

        queue.offer(root);
        valQueue.offer(root.val);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            Integer temp = valQueue.poll();
            if (node.left == null && node.right == null) {
                if (targetSum == temp) {
                    List<Integer> ans = new LinkedList<>();
                    TreeNode leaf = node;
                    while (leaf != null) {
                        ans.add(0, leaf.val);
                        leaf = map.get(leaf);
                    }
                    result.add(ans);
                }
            }
            if (node.left != null) {
                queue.offer(node.left);
                valQueue.offer(temp + node.left.val);
                map.put(node.left, node);

            }
            if (node.right != null) {
                queue.offer(node.right);
                valQueue.offer(node.right.val + temp);
                map.put(node.right, node);
            }
        }
        return result;
    }

    /**
     * 121. 买卖股票的最佳时机
     * <p>
     * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int result = 0;
        int minPrice = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > result) {
                result = prices[i] - minPrice;
            }
        }
        return result;
    }

    public int maxProfit2(int[] prices) {
        int result = 0;
        if (prices == null || prices.length == 0) {
            return result;
        }
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int sub = prices[j] - prices[i];
                if (sub > 0) {
                    result = Math.max(result, sub);
                }
            }
        }
        return result;
    }

    /**
     * 783. 二叉搜索树节点最小距离(树中任意两不同节点值之间的最小差值)
     * <p>
     * 二叉搜索树中序遍历，数组递增
     * <p>
     * https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
     *
     * @param root
     * @return
     */
    public int minDiffInBST(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        this.dfs(root, list);
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < list.size() - 1; i++) {
            min = Math.min(list.get(i) - list.get(i - 1), min);
        }
        return min;
    }

    public void dfs(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        this.dfs(node.left, list);
        list.add(node.val);
        this.dfs(node.right, list);
    }

    /**
     * 剑指 Offer 26. 树的子结构
     * <p>
     * https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/
     *
     * @param A
     * @param B 判断B是不是A的子结构
     * @return
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (this.recur(A, B) || this.isSubStructure(A.left, B) || this.isSubStructure(A.right, B));
    }

    private boolean recur(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null || A.val != B.val) {
            return false;
        }
        return this.recur(A.left, B.left) && this.recur(A.right, B.right);
    }


    /**
     * 1376. 通知所有员工所需的时间 TODO
     * <p>
     * https://leetcode-cn.com/problems/time-needed-to-inform-all-employees/
     *
     * @param n
     * @param headID
     * @param manager
     * @param informTime
     * @return
     */
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        return 0;
    }

    /**
     * 面试题 04.09. 二叉搜索树序列
     * https://leetcode-cn.com/problems/bst-sequences-lcci/
     *
     * @param root
     * @return
     */
    public List<List<Integer>> BSTSequences(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            list.add(new ArrayList<>());
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        return list;
    }

    private void visit(List<List<Integer>> list, Queue<TreeNode> queue, List<Integer> path) {
        if (queue.isEmpty()) {
            list.add(new ArrayList<>(path));
            return;
        }
        Queue<TreeNode> copyQueue = new LinkedList<>(queue);
        for (int i = 0; i < copyQueue.size(); i++) {
            TreeNode node = copyQueue.poll();
            if (node.left != null) {
                copyQueue.add(node.left);
            }
            if (node.right != null) {
                copyQueue.add(node.right);
            }
            path.add(node.val);
            this.visit(list, copyQueue, path);
            path.remove(path.size() - 1);
            queue = new LinkedList<>(copyQueue);
        }
    }


}
